package nachos.threads;

import nachos.machine.*;

import java.util.*;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the thread
 * that has been waiting longest.
 *
 * 一个优先队列给予每个线程一个优先级，下一个调度的线程有他们的优先级来决定。 优先级相同则根据等待时间来确定，等待时间较长的线程首先执行。
 *
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has the
 * potential to starve a thread if there's always a thread waiting with higher
 * priority.
 * 
 * 根本上来说，一个优先队列给予一个循环调度可以首先调用最高优先级的线程而忽略 其它线程的方法和能力，不过优先级调度存在使线程饥饿的可能性；
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 * 
 * 一个优先队列必须准确的解决优先级的繁衍问题，特别的，优先级必须被锁和jions 方法 赋予
 * 
 */
public class PriorityScheduler extends Scheduler {
	/**
	 * Allocate a new priority scheduler. 创建一个新的优先队列。
	 * 
	 */
	public PriorityScheduler() {
	}

	/**
	 * Allocate a new priority thread queue.
	 *
	 * 创建一个优先级队列
	 * 
	 * @param transferPriority
	 *            <tt>true</tt> if this queue should transfer priority from
	 *            waiting threads to the owning thread.
	 * @return a new priority thread queue.
	 */
	public ThreadQueue newThreadQueue(boolean transferPriority) {
		return new PriorityQueue(transferPriority);
	}

	public int getPriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getPriority();
	}

	public int getEffectivePriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getEffectivePriority();
	}

	public void setPriority(KThread thread, int priority) {
		Lib.assertTrue(Machine.interrupt().disabled());

		Lib.assertTrue(priority >= priorityMinimum && priority <= priorityMaximum);

		getThreadState(thread).setPriority(priority);
	}

	public boolean increasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMaximum)
			return false;

		setPriority(thread, priority + 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}

	public boolean decreasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMinimum)
			return false;

		setPriority(thread, priority - 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}

	/**
	 * The default priority for a new thread. Do not change this value.
	 * 
	 * 对于一个线程默认的优先级
	 * 
	 */
	public static final int priorityDefault = 1;
	/**
	 * The minimum priority that a thread can have. Do not change this value.
	 * 
	 * 优先级的最小值
	 * 
	 */
	public static final int priorityMinimum = 0;
	/**
	 * The maximum priority that a thread can have. Do not change this value.
	 * 
	 * 优先级的最大值
	 * 
	 */
	public static final int priorityMaximum = 7;

	/**
	 * Return the scheduling state of the specified thread.
	 *
	 * 返回一个特定的线程所在的优先级列表的ThreadState。
	 *
	 * @param thread
	 *            the thread whose scheduling state to return.
	 * @return the scheduling state of the specified thread.
	 */

	protected ThreadState getThreadState(KThread thread) {
		if (thread.schedulingState == null)
			thread.schedulingState = new ThreadState(thread);

		return (ThreadState) thread.schedulingState;
	}

	/**
	 * 
	 * 优先队列，按照线程的优先级排序
	 * 
	 * A <tt>ThreadQueue</tt> that sorts threads by priority.
	 */
	protected class PriorityQueue extends ThreadQueue {
		
		protected PriorityQueue()
		{}
		
		PriorityQueue(boolean transferPriority) {
			
			this.transferPriority = transferPriority;
			/*****************************************/
			cmp = new Comparator<ThreadState>() {
				@Override
				public int compare(ThreadState c1, ThreadState c2) {
					if (c1.getPriority() != c2.getPriority())
						return (int) (c1.getPriority() - c2.getPriority());
					else
						return (int) (c1.getTime() - c2.getTime());
				}
			};
			que = new java.util.PriorityQueue<ThreadState>(priorityMaximum, cmp);
			/***************************************/
		}

		public void waitForAccess(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			getThreadState(thread).waitForAccess(this);
		}

		public void acquire(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			getThreadState(thread).acquire(this);
		}

		public KThread nextThread() {
			Lib.assertTrue(Machine.interrupt().disabled());
			// implement me
			/***** add by beyhhhh *******/
			if (que.isEmpty()) {
				return null;
			} else {
				ThreadState kt = que.poll();
				kt.waitQueue = null;
				return kt.thread;
			}
			/***** add by beyhhhh *******/
			// OK;
		}

		/**
		 * Return the next thread that <tt>nextThread()</tt> would return,
		 * without modifying the state of this queue.
		 *
		 * @return the next thread that <tt>nextThread()</tt> would return.
		 */
		protected ThreadState pickNextThread() {
			// implement me

			/***** add by beyhhhh *******/
			if (que.isEmpty())
				return null;
			ThreadState a;
			a = que.poll();
			que.add(a);
			return a;
			/***** add by beyhhhh *******/
			// OK;
		}

		public void print() {
			Lib.assertTrue(Machine.interrupt().disabled());
			// implement me (if you want)
		}

		/*
		 * <tt>true</tt> if this queue should transfer priority from waiting
		 * threads to the owning thread.
		 */

		/***** add by beyhhhh *******/
		public boolean transferPriority;

		Comparator<ThreadState> cmp = null;
		java.util.PriorityQueue<ThreadState> que = null;
		/***** add by beyhhhh *******/
	}

	/**
	 * The scheduling state of a thread. This should include the thread's
	 * priority, its effective priority, any objects it owns, and the queue it's
	 * waiting for, if any.
	 *
	 * @see nachos.threads.KThread#schedulingState
	 */
	protected class ThreadState {
		/**
		 * Allocate a new <tt>ThreadState</tt> object and associate it with the
		 * specified thread.
		 *
		 * @param thread
		 *            the thread this state belongs to.
		 */

		public ThreadState(KThread thread) {
			this.thread = thread;

			setPriority(priorityDefault);
		}

		/**
		 * Return the priority of the associated thread.
		 *
		 * @return the priority of the associated thread.
		 */
		public int getPriority() {
			return priority;
		}

		public long getTime() {
			return time;
		}

		/**
		 * Return the effective priority of the associated thread.
		 *
		 * @return the effective priority of the associated thread.
		 */
		public int getEffectivePriority() {

			// implement me
			
			return priority;
		}

		/**
		 * Set the priority of the associated thread to the specified value.
		 *
		 * @param priority
		 *            the new priority.
		 */
		public void setPriority(int priority) {
			if (this.priority == priority)
				return;
			/***** add by beyhhhh *******/
			if (this.waitQueue != null && this.waitQueue.que != null) {
				this.waitQueue.que.remove(this);
				this.priority = priority;
				this.waitQueue.que.add(this);
			} else
				this.priority = priority;
			/***** add by beyhhhh *******/
			// implement me
			// OK;
		}

		public void setTime() {
			this.time = Machine.timer().getTime();
			return;
		}

		/**
		 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
		 * 
		 * the associated thread) is invoked on the specified priority queue.
		 * The associated thread is therefore waiting for access to the resource
		 * guarded by <tt>waitQueue</tt>. This method is only called if the
		 * associated thread cannot immediately obtain access.
		 *
		 * @param waitQueue
		 *            the queue that the associated thread is now waiting on.
		 *
		 * @see nachos.threads.ThreadQueue#waitForAccess
		 */
		public void waitForAccess(PriorityQueue waitQueue) {
			// implement me
			/***** add by beyhhhh *******/

			waitQueue.que.add(this);
			acquire(waitQueue);
			/***** add by beyhhhh *******/
			// OK;
		}

		/**
		 * Called when the associated thread has acquired access to whatever is
		 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
		 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
		 * <tt>thread</tt> is the associated thread), or as a result of
		 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
		 *
		 * @see nachos.threads.ThreadQueue#acquire
		 * @see nachos.threads.ThreadQueue#nextThread
		 */
		public void acquire(PriorityQueue waitQueue) {
			/***** add by beyhhhh *******/

			this.waitQueue = waitQueue;

			/***** add by beyhhhh *******/
			// implement me
			// OK;
		}

		/** The thread with which this object is associated. */
		protected KThread thread;
		/** The priority of the associated thread. */
		protected int priority;

		/***** add by beyhhhh *******/
		protected long time;
		protected PriorityQueue waitQueue;
		/***** add by beyhhhh *******/
	}
}
